Hard- 1851. Minimum Interval to Include Each Query

題意:給定一個二維陣列表示區間[left, right]\(表示left, right兩個數字)，區間的長度定義為right - left + 1
另給定一個陣列表示query，要回答每個query包含該數字的最小長度為何?
Sample Input:intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
說明: 
- Query = 2: [2,4] 是最小的區間包含 2，故答案為 4 - 2 + 1 = 3
- Query = 3: [2,4] 是最小的區間包含 3，故答案為 4 - 2 + 1 = 3
- Query = 4: [4,4] 是最小的區間包含 4，故答案為 4 - 4 + 1 = 1
- Query = 5: [3,6] 是最小的區間包含 5，故答案為 6 - 3 + 1 = 4.

本題需要事先將queries和intervals排序，
每次進來一個新的query時，將舊的元素踢除(區間右界小於現在的query)，
嘗試加入新的可能元素(區間左界小於現在的query)，
由於需要一直新增、移除元素，
還要查詢最小值，故想到用「heap」結構

# 1851. Minimum Interval to Include Each Query 題解
from heapq import heappop, heappush
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        A = sorted(intervals)
        Q = sorted((q, i) for i, q in enumerate(queries))
        heap = []
        res = [-1] * len(Q)
        j = 0
        
        for query, idx in Q:
            while heap and heap[0][1] < query:
                heappop(heap)
            while j < len(A) :
                left, right = A[j]
                if left>query:
                    break
                if right>=query:
                    heappush(heap, (right - left + 1, right))
                j+=1
            if heap:
                res[idx] = heap[0][0]
        return res